/*
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。*/
#include <string>
#include <stack>
#include <iostream>

using namespace std;

class Solution {
public:
    int paris(char c) {
        if (c == ')') return '(';
        if (c == '}') return '{';
        if (c == ']') return '[';
        return 0;
    }

    bool isValid(string s) {
        stack<int> stk;

        for (int i = 0; i < s.size(); i++) {
            if (paris(s[i])) {
                if (stk.empty() || stk.top() != paris(s[i])) {
                    return false;
                }
                stk.pop();
            } else {
                stk.push(s[i]);
            }
        }

        return stk.empty();
    }
};

int main() {
    cout << Solution().isValid("({[]})") << endl;
    return 0;
}